package com.algorithm5;

import java.util.Arrays;

public class MergeSort {

    public static int[] mergeSort(int[] array){
        if(array.length<2)
            return array;
        int middle = (0+ array.length)/2;
        int[] left = Arrays.copyOfRange(array,0,middle);
        int[] right = Arrays.copyOfRange(array,middle,array.length);
        return merge(mergeSort(left),mergeSort(right));

    }
    public static int[] merge(int[] left,int[] right){
        int i = 0,j = 0,k=0;
        int leftLen = left.length;
        int rightLen = right.length;
        int[] temp = new int[leftLen+rightLen];
        while((i>=0 && i<leftLen)&&(j>=0&&j<rightLen)){
            if(left[i]<right[j]){
                temp[k++] = left[i++];
            }else{
                temp[k++] = right[j++];
            }
        }

        if(i==leftLen){//left全部拷贝完毕
            while(j<rightLen){
                temp[k++] = right[j++];
            }
        }
        if(j==rightLen){//right全部拷贝完毕
            while(i<leftLen){
                temp[k++] = left[i++];
            }
        }

        return temp;
    }

    public static void main(String[] args){
        int[] array = new int[]{4,3,6,8,9,7,10,5,1,2};
        System.out.println("array:"+ Arrays.toString(array));
        int[] result=mergeSort(array);
        System.out.println("sorted array:"+ Arrays.toString(result));
    }
}
